'''
难度 中等
题目链接 https://leetcode.cn/problems/number-of-dice-rolls-with-target-sum/description/
'''

from typing import List

class Solution:
    # 动态规划
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        '''
        第n个骰子的方案总数 = 前一个（n-1）骰子的方案数 + 最后一个骰子的方案 的总和 推导公式如下：
        f(n, target) = f(n - 1, target - 1) + ... + f(n - 1, target - k)
        '''
        模 = 10**9 + 7
        # 初始化
        f = [[0] * (target + 1) for _ in range(n + 1)]
        f[0][0] = 1
        # print(f)

        # 骰子的数量轮询
        for i in range(1, n + 1):
            # 目标和轮询 目标和区间
            for j in range(1, target + 1):
                # 每个骰子的可能值
                for x in range(1, k + 1):
                    if j - x >= 0:
                        f[i][j] = (f[i][j] + f[i - 1][j - x]) % 模
        # print(f)
        return f[n][target]

if __name__ == '__main__':
    s = Solution()
    参数 = [
        [1, 6, 3],
        [2, 6, 7],
        [30, 30, 500],
    ]
    预期 = [
        1,
        6,
        222616187,
    ]
    for k,v in enumerate(参数):
        r = s.numRollsToTarget(v[0], v[1], v[2])
        if r != 预期[k]:
            print("第{}个case不通过 期望={} 结果={}\n".format(
                k+1,
                预期[k],
                r
            ))